package chapter1.fundamentals.exercise;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

/**
 * @author quanlinlin on 2018/11/1 11:39.
 * @version 1.0
 */
public class E_22 {

    public static int rank(int key, int[] a) {
        return rank(key, a, 0, a.length - 1, 0);
    }

    /**
     * 递归查找一个数在有序数组中的排名
     * [0:10, 1:11, 2:12, 3:16, 4:18, 5:23, 6:29, 7:33, 8:48, 9:54, 10:57, 11:68, 12:77, 13:84, 14:98]
     *
     * @param key
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    private static int rank(int key, int[] a, int lo, int hi, int depth) {
        for (int i = 0; i < depth; i++) {
            System.out.print("\t");
        }
        int mid = lo + (hi - lo) / 2;
        System.out.printf("depth: %2d, lo: %2d, hi: %2d, mid: %2d\n", depth, lo, hi, mid);

        if (lo > hi) {
            return -1;
        }
        if (key < a[mid]) {
            return rank(key, a, lo, mid - 1, ++depth);
        } else if (key > a[mid]) {
            return rank(key, a, mid + 1, hi, ++depth);
        } else {
            return mid;
        }
    }

    public static void main(String[] args) {
        int[] whitelist = In.readInts(args[0]);

        //Arrays.stream(whitelist).forEach(System.out::println);

        Arrays.sort(whitelist);
        //System.out.println(ArrayUtil.arrayToString(whitelist));

        // read key; print if not in whitelist
        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            System.out.println("next number is :" + key);
            int rank = rank(key, whitelist);
            if (rank < 0) {
                StdOut.println(key + " not in whiteList");
            } else {
                StdOut.println(key + " location is " + rank);
            }
            System.out.println();
        }
    }
}
